package com.wtgroup.demo.mianshi.算法.排序;

/**
 * @author Nisus
 * @version 0.1
 * @date 2019/9/15 0:27
 */
public class QuickSort implements ComparableSort {
    /**
     * 小数组长度大于该值时采用插入排序
     */
    private final static int CUTOFF = 10;


    public static void sort(Comparable[] arr) {

        sort(arr, 0, arr.length-1);


    }

    private static void sort(Comparable[] arr, int left, int right) {

        if (right-left >= CUTOFF) {
            Comparable pivot = getPivot(arr, left, right);

            int l = left, r = right-1;
            while (true) {
                // 左边略过比pivot小的; 右边略过比pivot大的
                while (arr[++l].compareTo(pivot) < 0) {} // 遇到>=pivot时, 停止移动
                while (arr[--r].compareTo(pivot) >0 ) {}

                // 两边下标都停止移动时, 触发交换元素
                if (l<r) {
                    swap(arr, l, r);
                }else{
                    break;
                }
            }

            swap(arr, l, right-1);  // 至此, 枢纽元左边都<=它, 右边都>=它.

            // 左边 和 右边 部分分别重复
            sort(arr, left, l - 1);
            sort(arr, r+1, right);
        }else{
            InsertSort.sort(arr, left, right);
        }

    }





    /**采用 三数中值分割法 取枢纽元.
     * 1. 三数按顺序交换.
     * 2. 枢纽元放到 right-1 位.
     * @param arr
     * @return
     */
    private static Comparable getPivot(Comparable[] arr, int left, int right) {

        int mid = (left + right) / 2;
        if (arr[left].compareTo(arr[mid])>0) {
            swap(arr, left, mid);
        }
        if (arr[left].compareTo(arr[right])>0) {
            swap(arr, left, right);
        }
        if (arr[mid].compareTo(arr[right])>0) {
            swap(arr, mid, right);
        }

        swap(arr, mid, right-1);

        return arr[right - 1];
    }

    private static void swap(Comparable[] arr, int a, int b) {
        Comparable tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

}
